#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> stack;
        vector<int> ans;
        ans.resize(temperatures.size());

        stack.push_back(0);
        for (int i = 1; i < temperatures.size(); i++) {
            while (!stack.empty() && temperatures[i] > temperatures[stack.back()])
            {
                int idx = stack.back();
                ans[stack.back()] = i - idx;
                stack.pop_back();
            }
            stack.push_back(i);
        }
        for (int i = 0; i < stack.size(); i++) {
            int idx = stack[i];
            ans[idx] = 0;
        }
        return ans;
    }
};

void test01() {
    vector<int> input = {73, 74, 75, 71, 69, 72, 76, 73};
    Solution obj;

    vector<int> re = obj.dailyTemperatures(input);
    for (auto item : re) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
}

void test02() {
    vector<int> input = {30, 40, 50, 60};
    Solution obj;

    vector<int> re = obj.dailyTemperatures(input);
    for (auto item : re) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
}

void test03() {
    vector<int> input = {30, 60, 90};
    Solution obj;

    vector<int> re = obj.dailyTemperatures(input);
    for (auto item : re) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::cout << "this is Leetcode-739-demo." << std::endl;
    std::cout << "test01:" << std::endl;
    test01();

    std::cout << "test02:" << std::endl;
    test02();

    std::cout << "test03:" << std::endl;
    test03();
    return 0;
}
